ElmのArrayのindex accessパフォーマンス
#Elm
最近、index (a.k.a. offset, cursor) accessが可能で、かつ高速なデータ構造に興味があり、Arrayを再訪している
ElmのArrayのindex accessパフォーマンスはどうなってるのだろうか。ベンチしてみた。
https://ymtszw.github.io/elm_array_bench/
項目が多くなったので、結構時間がかかる
ソース: https://github.com/ymtszw/elm_array_bench
結果は下の方に画像付きで。まとめると、
Arrayでは、要素数のオーダー増加に対してindex accessの速度低下は定数倍以内に収まっている。O(1)
一方参考として挙げたListでは、当然要素数増加に比例してきれいにindex accessが遅くなっている(要素数100倍でaccess速度は1/100)。O(N)
Array.Hamtはindex accessに関してはビルトインのArrayに対して顕著な優位性があるわけではない。
固定長のInitializeに関しては、Array, Array.Hamt, ListいずれもO(N)で、Listが一番速い=オーバーヘッドが少ない模様
この部分のbenchは1回うまく実行できたのだがなぜかその後crashするようになってしまった
とりあえず、高速index accessできるcontainerがほしければ、ElmのArrayは十分実用的に見える
Array.Hamtの優位性はこの部分にはないようなので、あえて入れなくてもよさそう
MacBookPro mid-2014, 2.2 GHz Intel Core i7
https://gyazo.com/9f48a2d148cc1157631d15cc50a1fe74